#include<bits/stdc++.h>
using namespace std;
const int N = 1005;
const int M = 105;

int n,m;
int values[N];
int cost[N];
int ans[N];


int main(){
	scanf("%d%d",&n,&m);
	memset(ans,0,sizeof(ans));
	for(int i=1;i<=m;i++){
		scanf("%d%d",&cost[i],&values[i]);
		for(int j=n;j>=0;j--){
			if(j<cost[i]) break;
			ans[j] = max(ans[j], ans[j-cost[i]]+values[i] );
		}
	}
	printf("%d\n",ans[n]);
	return 0;
}